//============================================================================
// Name        : 7_1_2_Linux.cpp
// Author      : Eric Chen
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int SimapleArray[]={21,21,21,21,21,21,21,21,21,21,21,21};

class PrintInt
{
	public:
		void operator()(int elem) const
		{
			cout << elem<<' ';
		}
};

//i starts from one
int partition(vector<int>& vec,int p, int r)
{
	int x=vec[r-1];
	int i=p-1;
	for(int j=p;j<r;++j)
	{
		if(vec[j-1]<x)
		{
			++i;
			swap(vec[i-1],vec[j-1]);
		}
	}
	if((i==0)&&(vec[r-1]==vec[i]))
	{
		return (p+r)/2;

	}
	else
	{
		swap(vec[r-1],vec[i]);
		return i+1;

	}

}

int main() {
	vector<int> A;
	int size=sizeof(SimapleArray)/sizeof(int);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
    cout << "Array before sorting\n";
    for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	cout << "Partition the array is "<<partition(A,1,size)<<endl;
	cout << "Array after sorting\n";
	for_each(A.begin(), A.end(), PrintInt());

	cout<<endl;

    return 0;
}
